package everydayone.generateParenthesis;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2020/04/09
 * @author 王光浩 
 * @Thinking 使用备忘录模式
 */
public class MyMethodOTwo {
	private ArrayList<List<String>> memo=new ArrayList<List<String>>();
	public List<String> generateParenthesis(int n) {
		if(memo.size()>=n+1)return memo.get(n);
		if(n==0) {
			memo.add(new ArrayList<String>());
			return memo.get(0);
		}
		List<String> ret=new ArrayList<String>();
		for(int i=0;i<n;i++) {
			List<String> now=generateParenthesis(i);
			List<String> next=generateParenthesis(n-i-1);
			if(now.size()==0 && next.size()==0) {
				ret.add("()");
				memo.add(ret);
			}
			else if(now.size()==0) {
				for(String tem:next)ret.add("()"+tem);
			}
			else if(next.size()==0) {
				for(String tem:now)ret.add("("+tem+")");
			}
			else {
				for(int m=0;m<now.size();m++)
					for(int k=0;k<next.size();k++) 
						ret.add("("+now.get(m)+")"+next.get(k));
			}
		}
		memo.add(ret);
		return memo.get(n);
	}
}
